'''
https://leetcode.cn/problems/maximum-product-subarray/description/
'''

from typing import List
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0, 0] for _ in range(n)]
        dp[0][0] = nums[0]
        dp[0][1] = nums[0]
        for i in range(1, n):
            dp[i][0] = max(nums[i] * dp[i - 1][0], nums[i] * dp[i - 1][1], nums[i])
            dp[i][1] = min(nums[i] * dp[i - 1][0], nums[i] * dp[i - 1][1], nums[i])
        print(*dp,sep='\n')
        return max(max(row) for row in dp)

    def maxProduct2(self, nums: List[int]) -> int:
        n = len(nums)
        ans = nums[0]
        max_i, min_i = nums[0], nums[0]
        for i in range(1, n):
            max_j = max(nums[i] * max_i, nums[i] * min_i, nums[i])
            min_j = min(nums[i] * max_i, nums[i] * min_i, nums[i])
            max_i, min_i = max_j, min_j
            ans = max(max_i, ans)
        return ans

nums = [2,3,-2,4]
print(Solution().maxProduct(nums))